package org.aplombh.java.awcing.basic.graph.graphTraversal.dfs;

import java.util.Arrays;
import java.util.Scanner;

/**
 * n−皇后问题是指将 n 个皇后放在 n×n 的国际象棋棋盘上，使得皇后不能相互攻击到，即任意两个皇后都不能处于同一行、同一列或同一斜线上。
 * <p>
 * 1_597ec77c49-8-queens.png
 * <p>
 * 现在给定整数 n，请你输出所有的满足条件的棋子摆法。
 * <p>
 * 输入格式
 * 共一行，包含整数 n。
 * <p>
 * 输出格式
 * 每个解决方案占 n 行，每行输出一个长度为 n 的字符串，用来表示完整的棋盘状态。
 * <p>
 * 其中 . 表示某一个位置的方格状态为空，Q 表示某一个位置的方格上摆着皇后。
 * <p>
 * 每个方案输出完成后，输出一个空行。
 * <p>
 * 注意：行末不能有多余空格。
 * <p>
 * 输出方案的顺序任意，只要不重复且没有遗漏即可。
 * <p>
 * 数据范围
 * 1≤n≤9
 * 输入样例：
 * 4
 * 输出样例：
 * .Q..
 * ...Q
 * Q...
 * ..Q.
 * <p>
 * ..Q.
 * Q...
 * ...Q
 * .Q..
 */
public class NQueenProblem_843 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        NQueenProblem_1 nQueenProblem_1 = new NQueenProblem_1(n);
        nQueenProblem_1.dfs(0);

        NQueenProblem_2 nQueenProblem_2 = new NQueenProblem_2(n);
        nQueenProblem_2.dfs(0,0,0);
    }
}

/**
 * 全排列方式解决 Full permutation solution
 */
class NQueenProblem_1 {

    static final int N = 20;
    int n;
    char[][] graph; // 存储路径 storage path
    boolean[] column, diagonal, backDiagonal; // 标记该数字是否被使用过 Marks whether a number has been used

    NQueenProblem_1(int n) {
        this.n = n;
        graph = new char[N][N];
        for (char[] chars : graph) {
            Arrays.fill(chars, '.');
        }

        column = new boolean[N];
        diagonal = new boolean[N];
        backDiagonal = new boolean[N];
    }


    /**
     * 求解 solve
     *
     * @param u 第几行 which row
     */
    void dfs(int u) {

        // u==n： 已经放了n个皇后棋子
        if (u == n) {
            // 输出该路径 Output the path
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    System.out.print(graph[i][j]);
                }
                System.out.println();
            }
            System.out.println();
            return;
        }

        for (int i = 0; i < n; i++) {

            // u : row      -> x
            // i : column   -> y
            // 对角线为  diagonal       y =  x + b    -> b = y - x   -> 整体上移n move up n -> b = y - x + n -> i - u + n
            // 反对角线为 back-diagonal y = -x + b    -> b = y + x   -> u + i
            // 当前列、对角线、写对角线未被使用过
            if (!column[i] && !diagonal[u + i] && !backDiagonal[i - u + n]) {

                // 存储当前路径的节点 Stores the current path node
                // 便于遍历
                graph[u][i] = 'Q';

                // 标记当前节点已被使用 Mark the node is in use
                column[i] = diagonal[u + i] = backDiagonal[i - u + n] = true;

                dfs(u + 1);

                // 去除标记 Remove the mark
                column[i] = diagonal[u + i] = backDiagonal[i - u + n] = false;

                // 还原当前节点
                // 不影响下次遍历
                graph[u][i] = '.';
            }
        }
    }
}

/**
 * dfs方法
 */
class NQueenProblem_2 {

    static final int N = 20;
    int n;
    char[][] graph; // 存储路径 storage path
    boolean[] row, column, diagonal, backDiagonal; // 标记该数字是否被使用过 Marks whether a number has been used

    NQueenProblem_2(int n) {
        this.n = n;
        graph = new char[N][N];
        for (char[] chars : graph) {
            Arrays.fill(chars, '.');
        }

        row = new boolean[N];
        column = new boolean[N];
        diagonal = new boolean[N];
        backDiagonal = new boolean[N];
    }

    /**
     * dfs 依次遍历每个节点,
     * @param x 横坐标
     * @param y 纵坐标
     * @param s 皇后个数
     */
    void dfs(int x, int y, int s) {

        // 换行
        if (y == n) {
            y = 0;
            x++;
        }
        // 输出路径
        if (x == n) {
            if (s == n) {
                // 输出该路径 Output the path
                for (int i = 0; i < n; i++) {
                    for (int j = 0; j < n; j++) {
                        System.out.print(graph[i][j]);
                    }
                    System.out.println();
                }
                System.out.println();
            }
            return;
        }

        // 分两种情况, 第一种该点放皇后,另一种该点不放皇后
        // 第二种情况可能不满足, 直接跳过

        // 不放皇后
        dfs(x, y + 1, s);

        // 放皇后
        if (!row[x] && !column[y] && !diagonal[x + y] && !backDiagonal[x - y + n]) {

            graph[x][y] = 'Q';
            row[x] = column[y] = diagonal[x + y] = backDiagonal[x - y + n] = true;

            dfs(x, y + 1, s + 1);

            row[x] = column[y] = diagonal[x + y] = backDiagonal[x - y + n] = false;
            graph[x][y] = '.';
        }
    }
}